/*
https://leetcode.cn/problems/house-robber/submissions/562783821/
*198 打家劫舍
完成日期 24/9/5
*/
class Solution {
public:
    // 主函数，计算能够偷窃到的最高金额
    int rob(vector<int>& houseValues) {
        int n = houseValues.size();
        if (n == 1) {
            return houseValues[0];  // 如果只有一间房子，直接返回其价值
        }

        // 动态规划数组，用于存储到第 i 间房子为止能偷到的最高金额
        int dp[101] = {0};
        dp[0] = houseValues[0];  // 第一间房子的价值
        dp[1] = max(houseValues[0], houseValues[1]);  // 前两间房子中能偷到的最高金额

        // 动态规划填表
        for (int i = 2; i < n; i++) {
            // 状态转移方程：选择偷第 i 间房子（加上前两间房子的最高金额）或不偷第 i 间房子（保持前一间房子的最高金额）
            dp[i] = max(dp[i - 2] + houseValues[i], dp[i - 1]);
        }

        // 返回最后一间房子的最高金额
        return dp[n - 1];
    }
};